package com.daohuoren.algorithm;

import java.lang.Math;

class shell_sort {
	// 塞奇威克（Sedgewick） 步长序列函数
    public static int[] Sedgewick(int length) 
    {     
    	int[] arr = new int[length];
        int n,i = 0,j = 0;
        for(n = 0; n < length; n++)  
        {  
            if(n % 2 == 0)  
            {  
            	arr[n] = (int) (9 * ( Math.pow(4, i) - Math.pow(2, i) ) + 1); 
                i++;
            }  
            else  
            {  
            	arr[n] = (int) (Math.pow(2, j+2) * ( Math.pow(2, j+2) - 3 ) + 1); 
                j++;  
            }  
            if(arr[n] >= length)
            {  
                break;
            }
        }
        int[] a = new int[n];
        for(int k = 0; k < a.length; k++){
        	a[k] = arr[k];
        }
        System.out.println("步长序列：");
        printArray(a,0,1);
        return a;
    }
	public static void shell(int[] arr){
		int[] sedgewick = Sedgewick(arr.length);// 得到塞奇威克（Sedgewick） 步长序列数组
		int s,k,i,j,t;
		// 循环出所有步长
		for(s = sedgewick.length -1 ; s >= 0 ; s--){
			// 步长为sedgewick[s] 即分为 sedgewick[s] 个组
			System.out.println("分"+ sedgewick[s] +"组");
			for(k = 0; k < sedgewick[s]; k++){
				System.out.println("第"+ (k+1) +"组排序：");
				// 对每组数据进行排序
				printArray(arr,k,sedgewick[s]);
				for(i = k + sedgewick[s]; i < arr.length; i += sedgewick[s]){
					// 分组中，按插入排序排序数据，交换数据按步长 sedgewick[s]
			 		t = arr[i];
			 		j = i - sedgewick[s]; 
			 		while(j >= 0 && arr[j] > t){
			 			arr[j + sedgewick[s]] = arr[j];
			 			j-=sedgewick[s];
					}
			 		arr[j+sedgewick[s]] = t;
			 		printArray(arr,k,sedgewick[s]);
				}
				System.out.println();
			}
		}
		
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		 int[] arr = { 13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
		 System.out.println("原数据：");
		 printArray(arr,0,1);
		 shell(arr);
	}
	public static void printArray(int[] arr,int i, int j){
	    for(int n = i ; n < arr.length; n+= j){
	        System.out.print(arr[n]+"   ");
	    }
	    System.out.println();
	}
}
